package xiaohui

// 寻找全排列下一个数（找一个大于且仅大于原数的新整数）
// 1 从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界
// 2 让逆序区域的前一位和逆序区域中的大于它的最小的数字交换位置
// 3 把原来的逆序区域转为顺序区域
// 时间复杂度 On

func FindNearestNumber(numbers []int) []int {
	// 1
	var index = findTransferPoint(numbers)
	// 如果数字置换的边界为0，说明整个数组已经逆序，无法得到更大的相同数
	if index == 0 {
		return nil
	}
	// 2
	numbersCopy := make([]int, len(numbers))
	copy(numbersCopy, numbers)
	exchangeHead(numbersCopy, index)
	// 3
	reverse(numbersCopy, index)
	return numbersCopy
}

func findTransferPoint(numbers []int) int {
	for i := len(numbers) - 1; i > 0; i-- {
		if numbers[i] > numbers[i-1] {
			return i
		}
	}
	return 0
}

func exchangeHead(numbers []int, index int) []int {
	var head = numbers[index-1]
	for i := len(numbers) - 1; i > 0; i-- {
		if head < numbers[i] {
			numbers[index-1] = numbers[i]
			numbers[i] = head
			break
		}
	}
	return numbers
}

func reverse(numbers []int, index int) []int {
	i := index
	j := len(numbers) - 1
	for i < j {
		temp := numbers[i]
		numbers[i] = numbers[j]
		numbers[j] = temp
		i++
		j--
	}
	return numbers
}
